'''
https://leetcode.cn/problems/add-two-numbers-ii/
'''
from typing import Optional


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        def reverse(head):
            prev = None
            while head:
                next = head.next
                head.next = prev
                prev = head
                head = next
            return prev
        l1 = reverse(l1)
        l2 = reverse(l2)
        res = ListNode(-1)
        cur = res
        carry = 0
        while l1 or l2 or carry:
            val = 0
            val += l1.val if l1 else 0
            val += l2.val if l2 else 0
            val += carry
            carry = val // 10
            val = val % 10
            cur.next = ListNode(val)
            cur = cur.next
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next
        return reverse(res.next)


    def addTwoNumbers2(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        stack1 = []
        stack2 = []
        while l1:
            stack1.append(l1.val)
            l1 = l1.next
        while l2:
            stack2.append(l2.val)
            l2 = l2.next
        res_stack = []
        carry = 0
        while stack1 or stack2 or carry:
            val = 0
            val += stack1.pop() if stack1 else 0
            val += stack2.pop() if stack2 else 0
            val += carry
            carry = val // 10
            val = val % 10
            res_stack.append(val)
        res = ListNode(-1)
        cur = res
        while res_stack:
            cur.next = ListNode(res_stack.pop())
            cur = cur.next
        return res.next








